//--------------------------------------------------------------------
//
//  wtgraph.h
//
//  Class declaration for the adjacency matrix implementation of
//  the Weighted Graph ADT
//
//--------------------------------------------------------------------

const int defMaxGraphSize = 10,      // Default number of vertices
          vertexLabelLength = 11,    // Length of a vertex label
          filenameLength = 11,       // Length of a filename
          infiniteEdgeWt = 9999; 

//--------------------------------------------------------------------

class Vertex
{
  public:

    char label [vertexLabelLength];   // Vertex label
};

//--------------------------------------------------------------------

class WtGraph
{
  public:

    // Constructor
    WtGraph ( int maxNumber = defMaxGraphSize );

    // Destructor
    ~WtGraph ();

    // Graph manipulation operations
	int load(char *filename);
    void insertVertex ( Vertex newVertex );           // Insert vertex
    void insertEdge ( char *v1, char *v2, int wt );   // Insert edge
    int retrieveVertex ( char *v, Vertex &vData ) const;
                                                      // Get vertex
    int edgeWeight ( char *v1, char *v2, int &wt );
                                                      // Get edge wt.
    void removeVertex ( char *v );                    // Remove vertex
    void removeEdge ( char *v1, char *v2 );           // Remove edge
    void clear ();                                    // Clear graph

    // Graph status operations
    int empty () const;                           // Graph is empty
    int full () const;                            // Graph is full
	void degree();					// output even/odd degree count


    // Output the graph structure -- used in testing/debugging
    void showStructure ();

  private:

    // Facilitator functions
    int index ( char *v ) const;       // Converts vertex label to an
                                       //   adjacency matrix index
    int& edge ( int row, int col );    // Set/get edge weight using
                                       //   adjacency matrix indices

    // Data members
    int maxSize,          // Maximum number of vertices in the graph
        size;             // Actual number of vertices in the graph
    Vertex *vertexList;   // Vertex list
    int *adjMatrix;       // Adjacency matrix
};

//--------------------------------------------------------------------
//
//  wtgraph.cpp
//
//  Adjacency matrix implementation of the Weighted Graph ADT
//
//--------------------------------------------------------------------

#include <iostream>
#include <fstream>
#include <string>
#include <assert.h>

using namespace std;

//--------------------------------------------------------------------

WtGraph:: WtGraph ( int maxNumber )

// Creates an empty graph. Allocates enough memory for maxNumber
// vertices (defaults to defMaxGraphSize).

  : maxSize(maxNumber),
    size(0)
{
    vertexList = new Vertex [ maxSize ];
    assert ( vertexList != 0 );

    adjMatrix = new int [ maxSize*maxSize ];
    assert ( adjMatrix != 0 );
}

//--------------------------------------------------------------------

WtGraph:: ~WtGraph ()

// Frees the memory used by a graph.

{
    delete [] vertexList;
    delete [] adjMatrix;
}

//--------------------------------------------------------------------

int WtGraph:: load ( char *filename )
{
    Vertex testVertex;            // Vertex
	char cmd, v1[vertexLabelLength], v2[vertexLabelLength];
	int wt;
	ifstream infile;
	infile.open(filename);
	infile >> cmd;
	while (cmd != '#')
	{
		if (cmd == 'v')
		{
			infile >> v1;
			strcpy(testVertex.label,v1);
			insertVertex(testVertex);
		}
		else 
		{
			infile >> v1 >> v2 >> wt;
			insertEdge(v1,v2,wt);
		}
		infile >> cmd;
	}
	infile.close();
	return 1;
}

//--------------------------------------------------------------------

void WtGraph:: degree()
{
	// ADD CODE HERE to Output the number of even and odd degree vertices
	/*
	even = track count of even degrees
	odd = track count of odd degrees
	degrees = temp var to track total degrees of a row
	row = row increment counter
	*/
	int even, odd, degrees, row;
	even = odd = degrees = row = 0;
	
	do
	{
		//loop cols
		for ( int i=0; i< size; ++i )
		{
			//if ( edge(row, i) != 0 )
			//{
				degrees += edge(row, i); 
			//}
		}

		if ( (degrees %2) ==0 ) { even++; }
		else { odd++; }

		row++; //increment row count
	}
	while(row < size); //loop rows

	cout << "Number of Even Degree Vertices = " << even << endl;
	cout << "Number of Odd Degree Vertices = " << odd << endl;
}

//--------------------------------------------------------------------

void WtGraph:: insertVertex ( Vertex newVertex )

// Inserts newVertex into a graph. If a vertex with the same label
// as newVertex already exists in the graph, then updates that
// vertex's data with newVertex's data.

{
    int pos,   // Position of the vertex in the vertex list
        j;     // Loop counter

    assert ( size != maxSize );   // Requires that graph is not full

    pos = index(newVertex.label);
    vertexList[pos] = newVertex;

    if ( pos == size )            // New vertex
    {
       size++;
       for ( j = 0 ; j < size ; j++ )
       {
           edge(size-1,j) = infiniteEdgeWt;
           edge(j,size-1) = infiniteEdgeWt;
       }
    }
}

//--------------------------------------------------------------------

void WtGraph:: insertEdge ( char *v1, char *v2, int wt )

// Insert an edge with the specified weight between vertices
// v1 and v2.

{
    int idx_v1 = index(v1),   // Index of vertex v1
        idx_v2 = index(v2);   // Index of vertex v2

    assert ( idx_v1 != size  &&  idx_v2 != size );

    edge(idx_v1,idx_v2) = wt;
    edge(idx_v2,idx_v1) = wt;
}

//--------------------------------------------------------------------

int WtGraph:: retrieveVertex ( char *v, Vertex &vData ) const

// Searches a graph for vertex v. If the vertex is found, then copies
// the vertex data to vData and returns 1. Otherwise, returns 0 with
// vData undefined.

{
    int pos,      // Position of the vertex in the vertex list
        result;   // Result returned

    pos = index(v);
    if ( pos != size )
    {
       vData = vertexList[pos];
       result = 1;
    }
    else
       result = 0;

    return result;
}

//--------------------------------------------------------------------

int WtGraph:: edgeWeight ( char *v1, char *v2, int &wt ) 

// If there is an edge connecting vertices v1 and v2, then returns 1
// with wt returning the weight of the edge. Otherwise, returns 0
// with wt undefined.

{
    int idx_v1 = index(v1),   // Index of vertex v1
        idx_v2 = index(v2);   // Index of vertex v2

    assert ( idx_v1 != size  &&  idx_v2 != size );

    wt = edge(idx_v1,idx_v2);
    return ( wt != infiniteEdgeWt );
}

//--------------------------------------------------------------------

void WtGraph:: removeVertex ( char *v )

// Removes vertex v from a graph.

{
    int idx_v = index(v),   // Index of vertex v
        j, k;               // Loop counters

    assert ( idx_v != size );

    for ( j = idx_v ; j < size-1 ; j++ )     // Shift vertex list up
        vertexList[j] = vertexList[j+1];

    for ( j = idx_v ; j < size-1 ; j++ )     // Shift rows up
        for ( k = 0 ; k < size ; k++ )
            edge(j,k) = edge(j+1,k);

    for ( j = idx_v ; j < size-1 ; j++ )     // Shift columns left
        for ( k = 0 ; k < size ; k++ )
            edge(k,j) = edge(k,j+1);

    size--;
}

//--------------------------------------------------------------------

void WtGraph:: removeEdge ( char *v1, char *v2 )

// Removes the edge between vertices v1 and v2 from a graph.

{
    int idx_v1 = index(v1),   // Index of vertex v1
        idx_v2 = index(v2);   // Index of vertex v2

    assert ( idx_v1 != size  &&  idx_v2 != size );

    edge(idx_v1,idx_v2) = infiniteEdgeWt;
    edge(idx_v2,idx_v1) = infiniteEdgeWt;
}

//--------------------------------------------------------------------

void WtGraph:: clear ()

// Removes all the vertices and edges from a graph.

{
    size = 0;
}

//--------------------------------------------------------------------

int WtGraph:: empty () const

// Returns 1 if a graph is empty. Otherwise, returns 0.

{
    return ( size == 0 );
}

//--------------------------------------------------------------------

int WtGraph:: full () const

// Returns 1 if a graph is full. Otherwise, returns 0.

{
    return ( size == maxSize );
}

//--------------------------------------------------------------------

void WtGraph:: showStructure () 

// Outputs a graph's vertex list and adjacency matrix. This operation
// is intended for testing/debugging purposes only.

{
    int wt,         // Edge weight
        row, col;   // Loop counters

    if ( size == 0 )
       cout << "Empty graph" << endl;
    else
    {
       cout << endl << "Vertex list : " << endl;
       for ( row = 0 ; row < size ; row++ )
           cout << row << '\t' << vertexList[row].label << endl;

       cout << endl << "Edge matrix : " << endl << '\t';
       for ( col = 0 ; col < size ; col++ )
           cout << col << '\t';
       cout << endl;
       for ( row = 0 ; row < size ; row++ )
       {
           cout << row << '\t';
           for ( col = 0 ; col < size ; col++ )
           {
               wt = edge(row,col);
               if ( wt == infiniteEdgeWt )
                  cout << "- \t";
               else
                  cout << wt << '\t';
           }
           cout << endl;
       }
    }
}

//--------------------------------------------------------------------
//
//  Facilitator functions
//

int WtGraph:: index ( char *v ) const

// Returns the adjacency matrix index for vertex v. Returns size if
// the vertex does not exist.

{
    int j;  // Loop counter

    for ( j = 0 ;
          j < size  &&  strcmp(vertexList[j].label,v) != 0 ;
          j++ );
    return j;
}

//--------------------------------------------------------------------

int& WtGraph:: edge ( int row, int col )

// Gets/sets adjMatrix[row][col].

{
    return adjMatrix[maxSize*row+col];
}



//--------------------------------------------------------------------
//
//  Test program for the operations in the Weighted Graph ADT
//
//--------------------------------------------------------------------

void WelcomeMsg();

void main()
{
    WtGraph testGraph(10);         // Test graph
    Vertex testVertex;            // Vertex
    char v1[vertexLabelLength],
         v2[vertexLabelLength],   // Vertex labels
		 filename[filenameLength], // Filename
         cmd;                     // Input command
    int wt;                       // Edge weight

	WelcomeMsg();

    cout << endl << "Commands:" << endl;
	cout << "  L       : Load a weighted graph" << endl;\
    cout << "  +v      : Insert (or update) vertex v" << endl;
    cout << "  =v w wt : Insert an edge with weight wt between "
         << "vertices v and w" << endl;
    cout << "  ?v      : Retrieve vertex" << endl;
    cout << "  #v w    : Display the weight of the edge between "
         << "vertices v and w" << endl;
    cout << "  -v      : Remove vertex v" << endl;
    cout << "  !v w    : Remove the edge between vertices v and w"
         << endl;
	cout << "  D       : Output the number of even and odd degree vertices" << endl;
    cout << "  C       : Clear the graph" << endl;
    cout << "  E       : Empty graph?" << endl;
    cout << "  F       : Full graph?" << endl;
    cout << "  Q       : Quit the test program" << endl;
    cout << endl;

    do
    {
        testGraph.showStructure();                   // Output graph

        cout << endl << "Command: ";                 // Read command
        cin >> cmd;
        if ( cmd == '+'  ||  cmd == '?'  ||  cmd == '-' )
           cin >> v1;
        else if ( cmd == '#'  ||  cmd == '!' )
           cin >> v1 >> v2;
        else if ( cmd == '=' )
           cin >> v1 >> v2 >> wt;
		else if (cmd == 'L' || cmd == 'l')
		{
			cout << "Enter filname: "; 
			cin >> filename;
		}

        switch ( cmd )
        {
          case '+' :                                 // insertVertex
               cout << "Insert vertex : " << v1 << endl;
               strcpy(testVertex.label,v1);
               testGraph.insertVertex(testVertex);
               break;

          case '=' :                                 // insertEdge
               cout << "Insert edge : " << v1 << " " << v2 << " "
                    << wt << endl;
               testGraph.insertEdge(v1,v2,wt);
               break;

          case '?' :                                 // retrieveVertex
               if ( testGraph.retrieveVertex(v1,testVertex) )
                  cout << "Vertex " << v1 << " exists" << endl;
               else
                  cout << "Vertex NOT found" << endl;
               break;

          case '#' :                                 // edgeWeight
               if ( testGraph.edgeWeight(v1,v2,wt) )
                  cout << "Weight = " << wt << endl;
               else
                  cout << "No edge between these vertices" << endl;
               break;

          case '-' :                                 // removeVertex
               cout << "Remove vertex " << v1 << endl;
               testGraph.removeVertex(v1);
               break;

          case '!' :                                 // removeEdge
               cout << "Remove the edge between vertices "
                    << v1 << " and " << v2 << endl;
               testGraph.removeEdge(v1,v2);
               break;

          case 'C' : case 'c' :                      // clear
               cout << "Clear the graph" << endl;
               testGraph.clear();
               break;

          case 'E' : case 'e' :                      // empty
               if ( testGraph.empty() )
                  cout << "Graph is empty" << endl;
               else
                  cout << "Graph is NOT empty" << endl;
               break;

          case 'F' : case 'f' :                      // full
               if ( testGraph.full() )
                  cout << "Graph is full" << endl;
               else
                  cout << "Graph is NOT full" << endl;
               break;

          case 'L' : case 'l' :                      // load
               if ( testGraph.load(filename) )
                  cout << "Graph loaded from " << filename << endl;
               else
                  cout << "Invalid input file" << endl;
               break;

          case 'D' : case 'd' :		  // output even/odd degree count
			   testGraph.degree();
               break;

          case 'Q' : case 'q' :                   // Quit test program
               break;

          default :                               // Invalid command
               cout << "Invalid command" << endl;
        }
    }
    while ( cmd != 'Q'  &&  cmd != 'q' );
}


void WelcomeMsg()
{
    cout << endl;
    cout << "===================================================" << endl;
    cout << "Welcome to the Graph Operations Program" << endl;
    cout << "Class Assignment: MATH 233 - iLab 5" << endl;
    cout << "Author: Ronald Ram" << endl;
    cout << "===================================================" << endl << endl;
}